#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//二叉搜索树的第k个结点，栈，非递归
TreeNode *KthNode(TreeNode *pRoot, int k)
{
    if (!pRoot)
    {
        return nullptr;
    }
    stack<TreeNode *> s;
    TreeNode *t = pRoot;
    int i = 0;
    while (t || !s.empty())
    {
        while (t)
        {
            s.push(t);
            t = t->left;
        }
        t = s.top();
        s.pop();
        ++i;
        if (i == k)
        {
            return t;
        }
        t = t->right;
    }
    return nullptr;
}

//递归
TreeNode *getkthnode(TreeNode *t, int k, int &i)
{
    if (!t)
    {
        return nullptr;
    }
    TreeNode *p;

    p = getkthnode(t->left, k, i);
    if (p)
    {
        return p;
    }

    ++i;
    if (i == k)
    {
        return t;
    }

    p = getkthnode(t->right, k, i);
    if (p)
    {
        return p;
    }

    return nullptr;
}

TreeNode *KthNode(TreeNode *pRoot, int k)
{
    int i = 0;
    return getkthnode(pRoot, k, i);
}

void test()
{
}

int main()
{
    test();
    return 0;
}